package com.ecnu.codelearn.utils;

/**
 * @author caopeisheng
 */
public class ModUtil {

    public static void main(String[] args) {
        for (int i = 1; ; i++) {
            if (i%199==86&&i%211==2){
                System.out.println(i);
                return;
            }
        }
    }

    /**
     * 模乘
     * @param x
     * @param y
     * @return x * y % MOD
     */
    public static long mul(long x, long y, long mod) {
        return ((x % mod) * (y % mod)) % mod;
    }

    /**
     * 模加
     * @param x
     * @param y
     * @return (x + y) % MOD
     */
    public static long add(long x, long y, long mod) {
        return  ((x % mod) + (y % mod)) % mod;
    }

    /**
     * 模快速幂
     * @param x
     * @param n
     * @return x^n % MOD
     */
    public static long quickPower(long x, long n, long mod) {
        if (n == 0) return 1;
        if (n == 1) return x % mod;
        long tmp = quickPower(x, n >> 1, mod);
        return (n & 1) == 0 ? mul(tmp, tmp, mod) : mul(x, mul(tmp, tmp, mod), mod);
    }

    /**
     * 分数求模
     * 费马小定理 a^(p-1) mod p = 1 mod p
     * a * a^(p-2) mod p = 1 mod p
     * a^(p-2) mod p = a^(-1) mod p
     * (b/a) % p = b * a^(-1) % p = b * a^(p-2) % p
     * @param a 分母
     * @param b 分子
     * @return (b/a) % MOD
     */
    public static long fractionMod(long a, long b, long mod) {
        return mul(b, quickPower(a, mod-2, mod), mod);
    }

    public static long foolishInverseMod(long a, long mod) {
        for (int i = 0; i < mod; i++) {
            if ((i*a)%mod == 1) {
                System.out.println(i);
                return i;
            }
        }
        return -1;
    }
}
